package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         402,
		Discription: "移除k位数字使得数字最小",
		Level:       2,
		Labels: map[string]int{
			"栈":   1,
			"单调栈": 1,
		},
	})
}

func RemoveKdigits(num string, k int) string {
	//维持一个非单调递减的栈
	incS := make([]byte, 0)
	deletedNum := 0
	for i := range num {
		if len(incS) == 0 || deletedNum == k {
			incS = append(incS, num[i])
			continue
		}

		//栈不为空，删除数没满、不满足非单调递减
		for len(incS) > 0 && incS[len(incS)-1] > num[i] && deletedNum < k {
			incS = incS[:len(incS)-1]
			deletedNum++
		}
		incS = append(incS, num[i])
	}

	//没删完，这时候栈都是非单调递减的，从后面开始删收益最大
	bytes := incS[:len(incS)-k+deletedNum]
	
	//去除前导0
	start := 0
	for i := range bytes {
		if bytes[i] == '0' {
			start++
		} else {
			break
		}
	}

	//特殊情况啥都不剩了
	str := string(bytes[start:])
	if str == "" {
		return "0"
	}

	return str
}
